package com.lh.demo;

import java.util.*;

/**
 * @author: linghao
 * @since: 2023/2/7
 *
 * 描述
 * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 */
public class 最长不含重复字符的子字符串JZ48 {


    //双指针+hash
    public int lengthOfLongestSubstring2 (String s){
        Map<Character,Integer> aMap = new HashMap<>();
        int max = 0;
        for(int i=0,j=0;i<s.length();i++){
            if(aMap.containsKey(s.charAt(i))){
                aMap.put(s.charAt(i),aMap.get(s.charAt(i))+1);
            }else{
                aMap.put(s.charAt(i),1);
            }
            //重复了就一直移动左边界 直到不重复
            while (aMap.get(s.charAt(i)) > 1){
                aMap.put(s.charAt(j),aMap.get(s.charAt(j))-1);
                j++;
            }
            max = Math.max(max,i-j+1);
        }
        return max;
    }

    //利用队列
    public int lengthOfLongestSubstring (String s) {
        // write code here
        Queue<Character> queue = new LinkedList<>();
        int max = 0;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            while (queue.contains(c)){
                queue.poll();
            }
            queue.add(c);
            max = Math.max(max,queue.size());
        }
        return max;
    }
}
